package leetcode.ge100;

class Solution_121 {

	public static void main(String[] args) {
		int[] prices = { 7, 1, 5, 3, 6, 4 };
		new Solution_121().maxProfit(prices);
	}

	public int maxProfit(int[] prices) {
		int l = prices.length;
		if (l < 1)
			return 0;
		int[] minPrices = new int[l];
		minPrices[0] = prices[0];
		for (int i = 1; i < l; i++) {
			minPrices[i] = Math.min(minPrices[i - 1], prices[i]);
		}
		int max = 0;
		for (int i = 1; i < l; i++) {
			max = Math.max(max, prices[i] - minPrices[i - 1]);
		}
		return max;
	}

}